[go: up one dir, main page]
Scribd
Upload
124 views3 pages

382 Syllabus

This document provides information about the COMP 382: Reasoning about Algorithms course offered in Fall 2022, including an overview of topics covered, course structure, policies, and evaluation breakdown. The course will focus on mathematically reasoning about algorithms to analyze correctness and efficiency through techniques like dynamic programming, greedy algorithms, and NP-completeness. Students will complete homework assignments, a midterm, and final exam while also participating in weekly labs.

Uploaded by

wendy
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
124 views3 pages

382 Syllabus

This document provides information about the COMP 382: Reasoning about Algorithms course offered in Fall 2022, including an overview of topics covered, course structure, policies, and evaluation breakdown. The course will focus on mathematically reasoning about algorithms to analyze correctness and efficiency through techniques like dynamic programming, greedy algorithms, and NP-completeness. Students will complete homework assignments, a midterm, and final exam while also participating in weekly labs.

Uploaded by

wendy
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

COMP 382: Reasoning about

Algorithms
Fall 2022

Konstantinos Mamouras and Michael Burke

Motivation
Writing algorithms is fun, but how do you show that your algorithm behaves correctly on all
possible inputs? Can you estimate your algorithm's worst-case runtime? Is it possible that
there is no efficient algorithm for the computing task that you are trying to solve? To answer
these questions, you have to mathematically reason about algorithms.

COMP 382 is an intermediate-level algorithms class with an emphasis on such mathematical


reasoning. The class teaches you many new algorithm design techniques, for example
advanced dynamic programming, greedy optimization, randomized algorithms, and reduction
to problems like linear programming. Along with these, you learn proof principles that you
can use to show that a given algorithm behaves correctly and efficiently, or that certain
algorithmic problems are unlikely to have efficient solutions.

Sequence of topics
1. Data Structures
2. Greedy Optimization
3. Dynamic Programming
4. Randomized Algorithms
5. Maximum Flow
6. NP-completeness

Lectures and Labs


The class is organized in two sections.

● Lectures for the two sessions are held together on Tuesdays and Thursdays,
10:50am-12:05pm, at DH 1055 (McMurtry Auditorium).

● The lab for Section 002 is from 4:00pm-5:15pm on Thursdays, and the lab for
Section 003 is from 5:30pm-6:45pm on Thursdays. The classroom for the labs is
TBD.
Canvas and Piazza
We will make heavy use of the Canvas and Piazza systems for this course. Specifically, all
course announcements will be made on Piazza. Course lecture slides and homeworks will
be made available through Canvas. We will also use Canvas to receive soft copies of
assignment submissions.

We will use Piazza to answer questions about the class.

In-class quizzes

To test your understanding, we will have in-class quizzes. These are not going to be graded.

Policy on attendance and laptops

In general, this class adopts a "no-open laptop" policy. The main exception to this policy is
that you can (need to!) use laptops for your in-class quizzes. The use of internet-connected
electronic devices is forbidden during exams.

We will not take attendance at the lectures. However, many of our lectures will have an
active learning component, and we will not follow a fixed textbook. Given this, you are
strongly encouraged to attend every lecture.

We will mark participation at labs. This participation will account for 10% of the course credit.

Evaluation

Assignments

We will have seven homework assignments, roughly one every two weeks. Late homework
will generally not be accepted. If there are extenuating circumstances, you should make
arrangements at least 48 hours in advance with the instructors. Only serious excuses will be
considered in cases where prior arrangements were not made.

You will need to submit soft copies of solutions on Canvas. Assignments need to be typed,
although you are allowed to use hand-drawn figures.
You should be as clear and concise as possible in your write-up of solutions.
Understandability of your answer is as desirable as correctness, because communication of
technical material is an important skill. A simple, direct analysis is worth more points than a
convoluted one, both because it is simpler and less prone to error and because it is easier to
read and understand. Points may be subtracted for solutions that are too long.

Collaboration and Honesty Policy

Collaboration on homework problems is permitted, but not encouraged. If you choose to


collaborate on some problems, you are allowed to discuss each problem with at most two
other students currently enrolled in the class. Before working with others on a problem, you
should think about it yourself for some time. Finding answers to problems on the Web or
from other outside sources (these include anyone not enrolled in the class) is strictly
forbidden. You must write up each problem solution by yourself without assistance, even if
you collaborate with others to solve the problem. You must also identify your collaborators. It
is a violation of this policy to submit a problem solution that you cannot orally explain to an
instructor or TA.

Examinations

In addition to the assignments, we will have one in-class midterm examination (we will
announce details about this later) and a final. No collaboration whatsoever is permitted on
exams. Violations of this policy will be dealt with according to university regulations.

Credit breakdown

The breakdown of credit in the course is as follows:

Homework assignments: 40%


In-class midterm: 25%
Final: 25%
Participation in labs: 10%

You might also like