DD2458 Problem Solving and Programming under Pressure 9.0 credits

Problemlösning och programmering under press

Successful problem solving in computer science requires a solid theoretical foundation as well as ability to apply the theory to practical problem solving.

The aim of this course is to develop your ability to apply knowledge of algorithms, data structures, and complexity theory to given problems. As a professional it is useful to be able to analyze a problem, judge the efficiency of proposed algorithms, and to implement them quickly and correctly. In this course, you will practice this by solving a number of homework assignments and while working under time constraints during problem solving sessions.

Note that this is an unusually heavy and work intensive course.

Show course information based on the chosen semester and course offering:

Offering and execution

No offering selected

Select the semester and course offering above to get information from the correct course syllabus and course offering.

Course information

Content and learning outcomes

Course contents *

Algorithms: computational geometry, graph algorithms, number theoretic algorithms, string matching. Design and analysis of algorithms: dynamic programming, amortized analysis, estimating the complexity of an algorithm. Programming skills mainly in C and Java.

Intended learning outcomes *

The overarching goal of the course is that the students should be able to use programming as a tool for problem solving, and should be able to apply theoretical knowledge from other computer science courses to solve practical problems.  The course has a large focus on going all the way from theory (in the form of algorithm design) to practice (in the form of a working program). 

After passing the course the student should be able to: 

  • use algorithm design methods such as greedy algorithms, dynamic programming, decomposition, and combinatorial search to construct algorithms for solving given problems, 
  • apply basic algorithms in areas such as graph theory, number theory, and geometry on given problems and adapt them to problem-specific circumstances, 
  • analyze the efficiency of different algorithms in order to decide which ones are sufficiently efficient in a given context, 
  • compare different problems with respect to difficulty, 
  • implement algorithms and data structures given abstract specifications, 
  • identify bugs in others' solution attempts on a problem, 
  • communicate with others during problem solving in groups, 
  • present algorithms, data structures, and problems verbally in a concise and lucid way.

The goals are attained by solving number of homework assignments, implementing a small library of algorithms and data structures, solving problems in groups during problem solving sessions, and by presenting solutions to homework assignments.

Course Disposition

No information inserted

Literature and preparations

Specific prerequisites *

One of the courses DD1352 Algorithms, Data Structures, and Complexity, DD2352 Algorithms and Complexity, or equivalent.

Recommended prerequisites

DD2440 Advanced Algorithms

Equipment

No information inserted

Literature

Course literature will be announced on the course web page at least 4 weeks before course start.

Examination and completion

Grading scale *

A, B, C, D, E, FX, F

Examination *

  • LAB1 - Programming Contests, 4.5 credits, Grading scale: A, B, C, D, E, FX, F
  • ÖVN1 - Exercises, 4.5 credits, Grading scale: A, B, C, D, E, FX, F

Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.

The examiner may apply another examination format when re-examining individual students.

The grade is based on the number of solved problems of the various kinds, and, to some extent, on the quality of the presentations. As the problems are of greatly varying difficulty, the student that solves many problems will automatically also solve a number of harder problems, thereby motivating the higher grade. For grade A one additionally needs to solve a given number of extra difficult problems.

In this course all the regulations of the code of honor at the School of Computer science and Communication apply, see: http://www.kth.se/csc/student/hederskodex/1.17237?l=en_UK.

Other requirements for final grade *

Examination can only be done during the course.

Opportunity to complete the requirements via supplementary examination

No information inserted

Opportunity to raise an approved grade via renewed examination

No information inserted

Examiner

Per Austrin

Further information

Course web

Further information about the course can be found on the Course web at the link below. Information on the Course web will later be moved to this site.

Course web DD2458

Offered by

EECS/Computer Science

Main field of study *

Computer Science and Engineering

Education cycle *

Second cycle

Add-on studies

Please discuss with the instructor.

Contact

Per Austrin, e-post: popup-17@csc.kth.se

Ethical approach *

  • All members of a group are responsible for the group's work.
  • In any assessment, every student shall honestly disclose any help received and sources used.
  • In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.

Supplementary information

The number of participants is limited to 25. 

The course is only given if we have sufficient teaching resources.

In this course, the EECS code of honor applies, see:
http://www.kth.se/en/eecs/utbildning/hederskodex