Algorithms: CS 5800

The course will use the Kleinberg/Tardos textbook on Algorithm Design (Addison Wesley) and will cover through chapter 13 but deleting some of the material from earlier chapters.

Internet Study Groups | Preparations

The material will be practiced through Piazza where students will take sides on algorithmic claims and then supporting their sides through actions. For a claim c, the students have two options: either they want to be verifier or falsifier of the claim c. If all want to be verifier or falsifier, we select two students to play a semantic game and we randomly force one student to take the opposite position. If there is at least one verifier and at least one falsifier they play one semantic game.

Semantic games are folklore knowledge. They are sometimes called Tarski games or Hintikka games.

The interaction through the semantic games allows the students to demonstrate their skills of defending their positions taken on claims. If a student wants to be verifier but cannot defend the claim, the student contradicts himself. Similarly, if a student wants to be falsifier but cannot refute the claim, th student contradicts herself.

My Background: I have done research in algorithms, a recent paper is here: @ARTICLE{lieber-specker:partial-2, TITLE = "{Complexity of Partial Satisfaction II}", AUTHOR = "Karl J. Lieberherr and Ernst Specker", JOURNAL = "Elemente der Mathematik", YEAR = 2012, PAGES = "134-150", VOLUME = 67, NUMBER = 3, doi = {10.4171/EM/202} } How Strong is an Egg? You have two identical eggs. Standing in front of a 100 floor building, you wonder what is the maximum number of floors from which the egg can be dropped without breaking it. What is the minimum number of tries needed to find out the solution?