COS 216: Algorithms

Spring 2022

Exam 1 information

1. Allowed materials

During the exam:

• You are strongly discouraged to use the textbook, your notes, homework, and PDFs I've given you.
• You are not allowed to use other resources (Internet search, friends, etc.).
• You may only use electronic devices (computer, smart phone) to the extent of following exam logistics (below).

2. Exam content

The exam covers everything we have done, up to and including Chapter 3. (Chapter 4 will be on the next exam.) Here are some topics we emphasized:

• stable matching problem: deferred acceptance algorithm, details of the algorithm, proof that the algorithm works
• algorithm analysis: worst-case running time, big Oh notation
  • the running time of any algorithm should be given in $O(.)$ notation; moreover:
  • while a $O(n^2)$ algorithm is also $O(n^5)$, write the first one as it is smaller
  • $O(n^2)$ and $O(23n^2+216n+55112)$ are the same, so write the first one as it is simpler
• data structures: abstract data types (ADTs) and common implementations, big Oh bounds of common operations
  • list ADT: implemented via array, linked list
  • stack ADT
  • queue ADT
  • priority queue ADT: implemented via heap
  • graph ADT: implemented via adjacency matrix, adjacency lists
• graphs:
  • big Oh bounds based on $n$ (number of vertices) only
  • big Oh bounds based on both $n$ and $m$ (number of edges)
  • traversal: BFS, DFS
  • connected components, bipartite testing
  • directed graphs: strongly connected components, topological order

As usual, please note that this document is not a contract. I may have inadvertently left something off that ends up on an exam question. Moreover, I will not be able to test all of this material given the time limitations of the exam. I will have to pick and choose some subset of it.

3. Logistics

The exam will take place during our usual class time. I will proctor you via Zoom.

Before class time:

• Read this document carefully. Ignorance is not an excuse.
• Prepare enough paper to write on.
• On the first sheet, write at the top an academic integrity statement of your own devising. You should say that you didn't consult any unauthorized resources (Internet search, friends, other sources of help, etc.).
• Sign your name after the statement.

At class time:

• Join our usual Zoom meeting first.
• Find a PDF of the exam questions on Moodle near the bottom; pull it up on your computer.
• Work things out on notebook/blank paper. You do not need to print out the questions.
• After you are done or the time is up, scan your work and upload to Moodle near the bottom.
• Download your submission from Moodle to double check that you uploaded correctly.
• You may leave early after you finish scanning and uploading your exam.

Scanning:

• Here are instructions for how best to scan handwritten work using a smart phone.
• It is different from simply taking pictures.
• Familiarize yourself with the procedure to make sure you feel confident scanning your work.
• If you would rather typeset your exam in $\LaTeX$, be my guest.

Timing:

• You have the full 50 minutes of class time for the exam.
• To give you more flexibility, since this class is scheduled within the 70-minute C4 block, you may use the entire 70 minutes.
• To accommodate for scanning, you may submit up to 5 minutes after the 70 minutes end.
• Moodle will still accept submissions after the cutoff time, but it will be marked "late."
• If this happens, you should email me ASAP and explain why you were late, and assert that you did not spend any more than 70 minutes working on the exam.
• Summary:

  time	description
  11:10	Zoom opens, PDF of exam questions available on Moodle
  12:00	class/exam officially ends
  12:20	flex time ends, you must stop working
  12:25	deadline for submitting to Moodle

Proctoring:

• Please turn on your camera but mute your microphone.
• During the exam, don't unmute to talk to me: you will end up talking to everyone else as well.
• If you need to contact me, you can send me a message privately via the "chat" function in the Zoom meeting.
• Aim the camera at you, not your desk; don't hold up your work for others to see.
• Disconnect from the meeting after you've finished scanning and submitting to Moodle.

Tips:

• Label your questions clearly, especially if you are doing things out of order (try not to).
• Show your work.
• Do not write in columns.
• Even though you are under time pressure, try to write legibly; if I can't read your handwriting, I can't give you credit.
• Make sure your scan is legible. If I can't open your PDF or read your content, I can't give you credit.
• After submitting, download the PDF from Moodle and open it up to make sure you submitted the right file and it contains all the pages.