In computer science, an algorithm is a set of sequences for a computer program to solve a class of problems. Finding good algorithms and knowing when to apply them will allow you to write interesting and important programs for real-world applications such as compressing videos, finding routes, rendering 3D objects, and scheduling multiple objects. This course aims to learn mathematical modeling of computational problems, covering common algorithms, algorithmic paradigms, and several data structures used to solve the problems. The course emphasizes the relationship between algorithms and programming, and introduces basic performance measures and analysis techniques for these problems.
Instructor Information
-
Name: Jinhong Jung
-
Contact: jinhongjung(at)jbnu.ac.kr
-
Office: #627, 7-th engineering building
Content
If you want to take this course in this semester, please read the followings carefully before the course enrollment time.
⚠️ Warning This course covers the theoretical area of computer science, i.e., it is not a programming subject.
Purpose
This course aims at the followings:
- Goal 1: To understand how to design and analyze an algorithm in terms of correctness and efficiency
- Goal 2: To learn ideas that effectively resolve challenges behind various classical problems
- Goal 3: To improve your computational thinking so that you can solve new problems by yourself
Prerequisites
Students are expected to have the following background:
- Good programming skills (C/C++, JAVA, Python, etc.), meaning you should be able to implement a pseudocode with your own language and debug or fix your codes by yourself.
- Familiarity with data structures (stack, queue, list, tree, heap, graph, hash, etc.), meaning you can implement commonly used data structures and analyze their time and space complexities at least for worst cases.
- Familiarity with basic discrete mathematics, meaning you should not be afraid to read and write mathematical expression when it comes to logical proof.
If you can solve the following problems by yourself, I believe that you are ready for this course.
- Searching the parent for each node: https://www.acmicpc.net/problem/11725
- DFS and BFS: https://www.acmicpc.net/problem/1260
If you had difficulty catching up with the Data Structure course or solving the above problems, this course could be very tough, and you may need to invest a lot of effort and time in this class (of course, this class is well worth doing that, but it will be quite painful in this case). If you must take this course, but you feel like you are not ready, then please consider studying the following by yourself in advance (note that this is not mandatory, but it will definitely help you learn about this course).
- Solve representative problems at https://www.acmicpc.net/step. Target steps are as follows:
| Topics | Programming | Math | Data Structure |
|---|---|---|---|
| Steps | 1, 2, 3, 4, 5, 6, 7, 10 | 8, 9 | 17, 18, 21, 23, 27 |
⚠️ Warning This course does not cover the aforementioned preliminaries in detail.
Reference Text
- 관계 중심의 사고법 - 쉽게 배우는 알고리즘, 문병로, 한빛아카데미
Logistics
- All lectures are offered online via Zoom, and exams are taken offline. Each lecture will be recorded, and then uploaded to Youtube after the lecture.
- Korean is used by default in all aspects (notifications, lectures, assignments, and exams), except that lecture materials such as slides are written in English for readability and improving your familiarity with English materials.
- All notifications, schedules, and materials are uploaded to an LMS (e.g., https://ieilms.jbnu.ac.kr/). Please check the bulletin board regularly (of course, I will notify you of some information using a mobile messenger if necessary, but not all). Note that a non-negligible penalty will be assigned if you miss a deadline (refer to its origin).
- If you have questions and ideas for this course, you can join the following CLASSUM and post your opinions freely (also, it is possible to anonymize your identification). I am willing to accept any reasonable suggestion if it can help your learning about this course.
Evaluation Plan
This course is based on relative evaluation (상대평가), and detailed grade ratios will be announced in a lecture.
| Attendance | Homework | Midterm Exam | Final Exam |
|---|---|---|---|
| 5% | 25% | 35% | 35% |
- The maximum total score is 100 points.
- Disqualification policies
- Any form of cheating for each task (e.g., homework and exam) will give the corresponding task a zero point, and it could be reported to our school’s disciplinary committee.
- If you have absences of more than a quarter (1/4) of all lectures, then F grade will be assigned.
- If your total score is less than 10 points, then F grade will be assigned (note that there is no room for compromise).
Schedule (Tentative)
| Date | Description | Content | Method | Homework |
|---|---|---|---|---|
| 1 | Introduction to Algorithm | Course overview Introduction to algorithm Asymptotic analysis |
Online | |
| 2 | Recurrence and Mathematical Preliminaries |
Recurrence and its analysis Math used for logical proof |
Online | HW1 |
| 3 | Sort I | Basic sorting algorithms (selection/bubble/insertion) Advanced sorting algorithms (heap/merge/quick) |
Online | |
| 4 | Sort II | Lower bound of comparison based sorting Special sorting (counting/radix) |
Online | HW2† |
| 5 | Selection and Advanced Data Structure I |
Linear time selection algorithm Balanced binary search tree |
Online | |
| 6 | Advanced Data Structure II | Disjoint Set (union & find) | Online | HW3† |
| 7 | Dynamic Programming | Concept and basic problems Advanced problems |
Online | HW4† |
| 8 | Review & Midterm | Offline midterm exam | Offline | |
| 9 | Graph I | Minimum spanning tree (Prim/Kruskal) Topological sort Strongly connected component |
Online | |
| 10 | Graph II | Single source shortest path (Dijkstra/Bellman-Ford) All pair shortest path (Floyd-Warshall) |
Online | HW5† |
| 11 | Greedy Algorithm | Concept and greedy structure Related problems |
Online | |
| 12 | String Matching | Naive algorithm and automata Advanced algorithms (Rabin-Karp/Boyer-Moore) |
Online | HW6† |
| 13 | NP | Decision problem, NP, and polynomial reduction NP-hard/NP-complete, and problems |
Online | HW7 |
| 14 | State Space Tree | Backtracking/Branch and Bound A* algorithm for shortest path and traveling salesman |
Online | |
| 15 | Review & Final | Offline final exam | Offline |
- If a homework has † symbol, it indicates a programming assignment automatically evaluated by an online judge system (e.g., http://litmus.jbnu.ac.kr). Otherwise, it is a report assignment to be solved manually.
- This schedule may be subject to change depending on progress.