Algorithms

Welcome to this course! This course is an introduction to algorithm design. In this course, we study rigorous analysis of algorithms based on formal mathematical proofs. 

General Information:

• Instructor: Jiapeng Zhang. ( jiapengz@usc.edu )

• Time: Mon/Wed 5:30 - 6:50 pm

• Location: THH 102

• Discussion: Friday 2:00 -3:50 pm at  THH 301

• Office hours: Monday 3:00 - 5:00 pm at SAL 316

• Piazza: link.

Student Team:

• Barrett Wang (mwang424@usc.edu).

  • Office hours: Thursday 10:00 - 12:00 am at SAL 316.

• Xu Wang (xwang032@usc.edu).

  • Office hours: Tuesday 1:00 - 3:00 pm at EEB 206.

• Grace Zhang (gracez@usc.edu).

  • Office hours: Friday 10:00 - 12:00 am at SAL 322.

Reading Materials:

• Textbook: Algorithm Design, by Jon Kleinberg and Éva Tardos.

Evaluation:

• Homework (0%). There will be nine homework assignments. This is a theory class, and the homework problems will be proof-based. Homework submissions are not mandatory; however, you will receive feedback on your submission, which can be valuable for understanding the material and preparing for exams.

• Three midterm exams (20% each): There will be three midterm exams, each containing 3-4 problems. Almost all of the problems be the same as (or very similar to) the problems from the homework sets. Only one problem will be new.

• Final exam (40%): It will cover the material of the entire semester.

Based on the weighted percentage, the following table tells you the final grade. If our exams are more difficult than anticipated, we might make the scale slightly more lenient, but it will definitely not become more strict.

Percentage       Grade

86%                      A

79%                      A-

72%                      B+

65%                      B

58%                      B-

54.5%                  C+

51%                      C

47.5%                  C-

40%                      D

<33%                    F

Regrades:

If you feel that there are mistakes in your grades, you are welcome to request a regrade. Here are the relevant policies:

• Regrade requests must be made in person during any office hour.

• When requesting a regrade, please provide a clear explanation of why you believe the grade is incorrect. Regrade requests like "I need a higher score to get an A" will not be accepted.

Prerequisites:

Course requirementL

• CSCI 170 

• CSCI 104

You should be familiar and comfortable with the following:

• Writing rigorous proofs, including using techniques such as induction and contradiction.

• Big-O notation (the meanings of O, Ω, Θ, their differences and how to apply them).

• Basic set, function, sum, and product notation, and how to use/manipulate them.

• Basics about relations and their properties.

• Runtime analysis, and what it means to prove upper and lower bounds on the runtime of an algorithm.

• Basic combinatorics: counting, pairs, permutations, subsets, inclusion/exclusion, Pigeon Hole Principle.

• Basic probability: probability, events, independence, expectations, conditioning, Birthday Paradox.

• Data Structures and the operations they support, as well as the different implementations and their running times for the operations.

• In particular, you should know stacks, queues, heaps (priority queues), and maps. For maps, you should be comfortable with implementations as balanced search trees and hashtables, and understand their relative advantages.

• Breadth-First Search, Depth-First Search, Dijkstra's Algorithm

• The basic sorting algorithms: Insertion/Selection/Bubble Sort as well as Quick Sort, Merge Sort, and Heap Sort.