COSC 320 - 001 [3-2-0] Analysis of Algorithms

Academic Calendar Entry

Design and analysis of algorithms, illustrated from various problem areas. Models of computation, choice of data structures, space and time efficiency, computation complexity, algorithms for searching, sorting and graph-theoretic problems, NP-complete problems. [3-0-0]

Prerequisite: All of COSC 221, COSC 222 and one of MATH 221, APSC 179.

Course Objectives

This course introduces students to the body of knowledge of algorithm design and analysis, focusing on well-established design paradigms, analytic techniques for analyzing the correctness and the performance of algorithms, and general strategies for formulating real-world tasks as an algorithmic problem. Concepts and techniques will be discussed in the context of specific problems that arise from application domains.

Upon successful completion of this course, students are expected to demonstrate the ability to:

1.   formulate algorithmic problems properly;

2.   design and analyze algorithms using the techniques studied;

3.   convey algorithmic ideas formally; and

4.   describe algorithms and their implementation in a clear way.

Topics to be covered are as follows.

1.   Basics of Algorithms and Asymptotic Notation

2.   Divide and Conquer

3.   Randomized Algorithms (Tentative)

4.   Basic Graph Algorithms

5.   Greedy Algorithms

6.   Dynamic Programming

7.   Network Flow

8.   Theory of NP-completeness (Tentative)

Course Format

The course is in person. Practical skills and applications of topics are re-enforced with assignments and project work. Course materials are available on Canvas.

Midterm break and other calendar dates can be found at:http://okanagan.students.ubc.ca/calendar/.

Required Materials

•    Lecture notes (available electronically on Canvas)

•    Main Textbook: CLRS: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 3rd  Edition, 2009, ISBN: 9780262258104.

NOTE: The fourth edition of the textbook is available online throughUBC libraryfor free. The chapters we study are not much different in the 3rd  and 4th edition.

•     Your laptop or handheld devices such as tablets. This is used for the iClickers and class activities.

•     IPython Notebooks

•     The course uses iClicker Cloud (free).Setup instructions for iClicker Cloud Student Account.iClicker Cloud Login

Complementary Reading List:

•    Algorithms Illuminated, by Tim Roughgarden (Some parts are available online).

•    Algorithm Design, by Jon Kleinberg and Eva Tardos, Addison-Wesley, 2006 (preprint is available online).

•    Algorithms, by Dasgupta, Papadimitriou, Vazirani (Available online)

•    Mathematics for Computer Science, by Lehman, Leighton, Meyer (Available online)

•    Algorithms and Data Structures -The Basic Toolbox, Mehlhorn and Sanders (Available online)

Evaluation Criteria and Grading

Labs and assignments are due on the posted dates. Written assignments are to be submitted through Canvas. No late assignments or labs will be accepted. Attendance is expected in lectures.

Item 1: in-class exercises and iClickers (5%): These are questions or mini practices that you will work on in the class. You can form groups and solve these questions together. The in-class exercises can be collaboratively solved, but each student needs to submit the solutions individually. Otherwise, the student will receive no grade. This is only done during the class and should be answered and submitted during the class time. The goal is to have all exercises and questions to be submitted via iClicker.

Item 2: Assignments (30%): There are approximately 7 assignments in the course. You can form groups of 2 or maximum 3 to submit the assignments. There is no bonus for students who choose to submit their assignments individually.

Item 3: Midterm will be done in class and is closed book.

Item 4: Final exam is closed book and includes all materials, but less weight is considered for the contents that are covered in the midterm.

Assignment Expectation

For problems that ask you to prove an assertion, you are expected to give an informal proof explaining why the algorithm is correct. For problems that ask you to design an algorithm, you are expected to provide in  English the  idea of the algorithm, the  pseudo-code of the algorithm with  required data structures clearly specified, the analysis of its correctness (explaining in English) and running time, and an example to illustrate your algorithms.

Collaboration Policy

The assignments are designed to help students solidify their understanding of the course material. Some of the problems may be challenging, but not unrealistic. You are encouraged to collaborate with your peers on the assignment problems; Even more desirable is to form your own study group of two to three people with the same level of knowledge (not that one person solves, and others just look). A good practice is to write the solution in your own words to reenforce learning, so you will be able to explain the details of the solutions. You are also required acknowledge any help from the TA, the instructor, and the Web explicitly in your submissions. The exact same solutions that are copies of each other might be identified as cheating and receive a zero grade.

Note that only one person from the group requires to submit the solutions to the assignments. Remember to put all the names in the submission so all members receive the mark. The grades will be equal for all members of the groups. It is your responsibility to choose members who are working on the assignments collaboratively.

Exams

All exams are written and closed book. The examinations in this course are all closed-book, so you are NOT permitted to access any of the course materials, including your notes, during the exam.

Final grades will be based on the evaluations listed above and the final grade will be assigned according to the standardized grading system outlined in the UBC Okanagan Calendar. The Barber School reserves the right to scale grades in order to maintain equity among sections and conformity to University, faculty, department, or the school norms. Students should therefore note that an unofficial grade given by an instructor might be changed by the faculty, department, or school (See UBC Calendar for the exam period: http://www.calendar.ubc.ca/okanagan/index.cfm?tree=3,41,90,1014).

Note: Any requests for changes to final exams must be sent to the office of the Associate Dean of Students ([email protected]).

Passing Criteria

Students MUST achieve at least 50% of the final exam grade to pass the course. Failure to do so will result in a 45% grade, or the resulting grade, whichever is the lowest.