På Svenska

DD2458 Problem Solving and Programming under Pressure 9.0 credits

Problemlösning och programmering under press

Please note

The information on this page is based on a course plan that is not yet valid.

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.

  • Educational level

    Second cycle

  • Academic level (A-D)

    C

  • Subject area

  • Grade scale

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

Course offerings

Spring 13 popup for programme students

  • Periods

    Spring 13 P3 (4.5 credits), P4 (4.5 credits)

  • Application code

    61374

  • Start date

    2013 week: 2

  • End date

    2013 week: 22

  • Language of instruction

    Swedish

  • Campus

    KTH Campus

  • Number of lectures

  • Number of exercises

  • Tutoring time

    Daytime

  • Form of study

    Normal

  • Number of places *

    Max. 30

    *) If there are more applicants than number of places selection will be made.

  • Schedule

    Schedule (new window)

  • Course responsible

    Per Austrin <austrin@kth.se>

  • Teacher

    Per Austrin <austrin@kth.se>

  • Target group

    All who have the required prior knowledge.

    The number of participants is limited to 30. Ask the course leader about the selection principle! Manual selection.

    (Modular schedule in module E and J.)

Autumn 13 popuph13 for programme students CANCELLED

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, 
  • describe algorithms, data structures, and problems in writing 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 writing solution descriptions for a homework assignment.

Course main content

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.

Eligibility

Prerequisites

One of the courses 2D1352/DD1352 Algorithms, data structures and complexity and 2D1354/DD2354 Algorithms and complexity, or the equivalent.

Literature

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

Examination

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

The grade is based on the number of solved problems of the various kinds, and, to some extent, on the quality of the solution descriptions. 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.

Requirements for final grade

Examination can only be done during the course.

Offered by

CSC/Computer Science

Contact

Per Austrin, e-post: austrin@kth.se

Examiner

Per Austrin <austrin@kth.se>

Supplementary information

The number of participants is limited to 30. 

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

Add-on studies

Please discuss with the instructor.

Version

Course plan valid from: Autumn 13.
Examination information valid from: Autumn 07.