Design and Analysis of Computer Algorithms

Spring 2017, lectured by Prof. H. Choo

This is a fundamental and important course for undergraduate students with prior knowledge of C and Data Structures. This course provides significant basic concepts of computer science and engineering, the philosophy behind the theory, and actual applications to real world. During the course students can learn the design of advanced data structures, the techniques for designing and analyzing the efficiency of algorithms, the methods of obtaining efficient algorithms. The main purpose of this course is to introduce key algorithms which are essential for solving computeroriented problems, and techniques for easier creation of other efficient algorithms. We cover advanced techniques behind data structures for analyzing upper and lower bounds for many essential algorithms in this area. Problems discussed during the semester include sorting, searching, advanced data structures, dynamic programming, divide-and-conquer method, greedy methods, graph algorithms, and maximum flow problem.

Office Information

Office: Engineering II (27304) / Phone: (031)290-7145
Office hour: TBA
Teaching assistant: Dang Thien Binh (26317, )


Textbook

Introduction to Algorithms, 3rd Edition
by T.H.Cormen, C.E. Leiserson,
R.L. Rivest, MIT Press, 2009


 

Announcements

5. ITRC forum
– May 23 -> May 27
– Your name are registered
– May 23, no class but onsite visit and see the change
4. Programming Exam
– Programming exam time: 13h30, May 20, 2017
– Programming exam rooms: 21514, 22111, 23529
– Student list is in the attachment. Check which is your room for the programming exam. Audits are in the room 23529
– I will create an assignment “Programming Exam 2017″ and you will submit your programs to this assignment. The assignment will be
closed when the programming exam finished
– You will use Visual Studio for programming exam. The guideline of creating C++ project is in the attachment. I made it on visual
studio 2015 but I believe the process is same with visual studio 2013 and visual studio 2010 (rooms 21514 and 22111 have Visual
Studio 2013 installed. For room 23529, most computers have Visual Studio 2010, but some have more recent versions installed​).
– You SHOULD practice the steps at home first to get familiar with how to use visual studio. It will save your time during the programming exam.
Student list
Guideline for programming exam

3. The makeup class will be on May 3rd, 2017 (same time (9:00AM) and same room​ (26515)).

2. The midterm exam will be held from 10:25 AM to 11:55 AM next Monday (April 17). There will be 2 rooms for the exam: 26312 and 26515. Students of groups 1, 3, 5 come to the room 26515 and students of groups 2, 4, 6 + audits come to the room 26312.​ You can find which group you belong to in this link.

1. No class on Wednesday, April 5th, 2017. The makeup class will be on May 3rd, 2017. Room will be announced later.

Lecture notes

Lecture 0. C Programming and Data Structures
Lecture 1. Introduction/Insertion Sort/Merge Sort
Lecture 2. Growth of Functions/Asymptotics
Lecture 3. Recurrences/Heapsort
Lecture 4. Quicksort
Lecture 5. Counting Sort/Radix Sort
Lecture 6. Hash Tables
Lecture 7. Binary Search Trees/AVL Trees
Lecture 8. Dynamic Programming
Lecture 9. Greedy Algorithm
Lecture 10. Elementary Graph Algorithm/Minimum Spanning Trees