Algorithm Design, first semester, 2010

Submitted by admin on Sat, 1 May 2010 - 16:33

News (latest first)

cafe grader is available at http://www.nattee.net/grader For discussion, please use the main webboard Email is encouraged, please start your subject by [algo] and include your real name and id as well

(15-09-2010) Slide and lecture note #3 of search is available.
(13-09-2010) Lecture note for search is available, graph lecture note #3 is also online.
(29-08-2010) Slides and lecture notes of graph algorithm and shortest path and greedy are available.
(27-08-2010) Homework #6 is published.
(13-08-2010) Graph: slide and lecture note are available.
(12-08-2010) Homework #5 is published.
(25-07-2010) add more slides for Dynamic Programming
(21-07-2010) Homework #4, Lecture note #2 is available. (see below)
(14-07-2010) Lecture note #1 is available. (see below)
(13-07-2010) Homework #3 is extended to monday (19 Jul).
(08-07-2010) Homework #3 is available. Due date is 14 Jul.
(05-07-2010) Full syllabus is available here
(16-06-2010) Homework #1 is available. Nobody opts out of homework system. This marks the end of opt-out period. For section 3, we won't have a class on 18 Jun and 25 Jun. On 27 Jun, we will have the second quiz.
(10-06-2010) Tomorrow we will have first quiz. Please check this file for your seating. Quiz will start exactly at 0900. This is test run, anybody attending the quiz will get full score regardless of their submission.
(09-06-2010) Syllabus --short version-- can be downloaded
(01-06-2010) list of username for grader system is available.
(31-05-2010) The first set of h/w is available. This one does not count for final scoring.
(31-05-2010) Video and docs for introduction is up!.
(18-05-2010) Course syllabus will be available soon.
(18-05-2010) The student are required to finish homework 00 before semester begin.

Resource

Download course syllabus here.
Lab docs of 2009 can be found here
Introduction to cafe-grader is here. You can also download dev-c++ and grader introduction video.
Our local copy of Bloodshed Dev-C++

C++ Resource

!!!Read this first!!! Our Hello, CP! tutorial, which is the first lab of the 2009. This will guide you through your first C program. The IDE used in the lab is Dev-C++
An Introduction to C Programming for Java Programmers is a good starting point since you all are familiar with JAVA
Website cprogramming.com has very good tutorials. We suggest reading lesson 1 to lesson 10.
Array and pointer in C is more complex than that of JAVA, check this one for a good introduction.
The C Book, another book for C beginners.
Thinking in C++ by Bruce Eckel, a must-read for most C++ developers. The second edition of the book can be downloaded for free.

C++ Development platform

Dev-C++ is the recommended platform
Code::Blocks is also a good alternative

Quizzes

The first quiz (11 Jun) is here. Its solution is also available.
The second quiz (25 Jun) will be available soon.

Assignment

Solution and test data will be available when the submission of the particular problem is closed. Solution marked by [ref] means it is the reference solution. Be noted that there are definitely more than one ways to solve the problem.

Name Issue Date Due Date Solution Test Data hw00a_helloworld pdf 18 May 2010 7 Jun 2010 ref hw00b_fibo pdf 18 May 2010 7 Jun 2010 ref hw00c_drawbox pdf 18 May 2010 7 Jun 2010 ref hw00d_timeafter pdf 31 May 2010 7 Jun 2010 ref hw00e_BMI pdf 31 May 2010 7 June 2010 ref hw00f_aminmax pdf 31 May 2010 7 Jun 2010 ref hw01a_palindrome pdf 16 Jun 2010 27 Jun 2010 hw01b_drawtri pdf 16 Jun 2010 27 Jun 2010 hw01c_minmax2 pdf 16 Jun 2010 27 Jun 2010 hw02a_drawstar pdf 30 Jun 2010 7 Jul 2010 hw02b_sudoku pdf 30 Jun 2010 7 Jul 2010 hw02c_nodemax pdf 30 Jun 2010 7 Jul 2010 hw03a_pairsum pdf 8 Jul 2010 14 Jul 2010 hw03b_tiling pdf 8 Jul 2010 14 Jul 2010 hw03c_sds pdf 8 Jul 2010 14 Jul 2010 hw04a_lcs pdf 21 Jul 2010 4 Aug 2010 hw04b_barcode pdf 21 Jul 2010 4 Aug 2010 hw04c_denomination pdf 21 Jul 2010 4 Aug 2010 hw05a_path pdf 12 Aug 2010 18 Aug 2010 hw05b_dilation pdf 12 Aug 2010 18 Aug 2010 hw05c_friends pdf 12 Aug 2010 18 Aug 2010 hw06a_wall pdf 27 Aug 2010 3 Sep 2010 hw06b_virus pdf 27 Aug 2010 3 Sep 2010 hw06c_exchange pdf 27 Aug 2010 3 Sep 2010 hw07a_mst pdf 8 Sep 2010 15 Sep 2010 hw07b_sort pdf 8 Sep 2010 15 Sep 2010 hw07c_salesman pdf 8 Sep 2010 15 Sep 2010 hw08a_seqsum pdf 21 Sep 2010 15 Sep 2010 hw08b_knapsack pdf 21 Sep 2010 6 Oct 2010 hw08c_robot pdf 21 Sep 2010 6 Oct 2010

Lecture summary (Section 3)

Lecture note assignment is here. Lecture note should be handed in in the next lecture. If you wish to send via email, please include [algo] in the topic.

(09-06-2010) First meeting slide
(16-07-2010 -- 25-07-2010) Analysis Introduction slide
(30-06-2010 -- 02-07-2010) Converting program into Big-O slide
(07-07-2010 -- 14-07-2010) Divide and Conquer slide | lecture note #1 #2
(21-07-2010 -- 23-07-2010) Dynamic Programming slide slide MCM slide LCS | lecture note #1 #2
(04-08-2010 -- 11-08-2010) Graph algorithm slide lecture note #1 #2 #3
(11-08-2010 -- 25-08-2010) Shortest Path slide lecture note #1 #2
(27-08-2010) Greedy slide lecture note
(01-09-2010 -- 15-09-2010) Search slide lecture note #1 #2 #3 #4
(15-09-2010 -- 17-09-2010) NP Complete slide lecture note