VE477 Project (part 1)

1 Setup

Important note: At the end of each part this document will be re-issued with completed tasks crossed out. Please to not forget to always refer to the latest version available. Please contact us if you think a problem has been misclassified, or if you feel any adjustment or clarification is needed.

1.1 Groups

Groups can be freely organised as long as the following rules are respected:

• No more than three students per group;

• Each group must register on Canvas (ve477 → People → Groups);

• A student must belong to exactly one group;

1.2 Problem selection

All the problems listed in section 3, are sorted by category and then by degree of difficulty. Solving an easy, not too hard, or hard problem will be rewarded by one, two, or three credits, respectively. No more than three credits can be selected from easy problems.

For each part of the project, students belonging to groups of one, two, or three students are expected to complete four, nine, or thirteen credits, respectively.

Each group needs to register on Canvas for each problem it selects. The group number used for regis-tration is the one assigned on Canvas (cf. subsection 1.1).

No more than three groups can select a same problem. If four or more groups select a problem, the remaining groups will wait in a queue and be called upon if one of the three first groups decides to change problem. Freely changing problems is allowed until October 2, November 6, and November 29, for part 1, 2 and 3, respectively. Past the deadline a problem is considered to belong to the three first groups which registered for it. It should however be reminded that the final total number of credits of a group must remain unchanged. For instance changing a hard problem for an easy one is not permitted, while changing it for one easy and one “not too hard” is allowed, in the limit of three easy problems per group.

It is not allowed for a group to select the same problem twice, i.e. if a group selects a problem in phase 1, or 2, it is not allowed to select it again in any of the subsequent phases, even if the problem remains open.

1

1.3 Catalog cover

This part of the project is not mandatory and only based on voluntary participations.

The goal of this project being the creation of a catalog it should feature a front page showing the following information: (i) a name, (ii) the course reference, and (iii) the academic year. All the rest of the design is left to your creativity…

You can freely propose covers by uploading a file on Canvas under the assignment “catalog cover” until the Saturday after the final exam. All the submissions will be made available for voting and the one with the most votes will be used as the official cover of the “Algorithm catalog” for the academic year 2020–2021. The designer(s) of the selected cover will be awarded a bonus.

2 Content

The goal being to construct a catalog listing problems together with their algorithmic solutions it is important that they are all treated following a similar pattern.

2.1 Catalog

A LATEX template is available on Canvas. For each problem provide:

• A clear and brief description of the problem as well as of its input and complexity;

• Information on where it occurs or example applications;

• Some precise pseudocode of an efficient algorithm solving it;

• Problems featuring a † should be explained with diagrams or graphs rather than pseudocode;

• References where this problems is described, solved, or discussed;

Note that the goal is to be able to refer to the catalog over a long period of time. It is therefore better to provide several links or references, privileging links which are less likely to disappear (scientific articles, books, wikipedia…)

Important instructions regarding the template file:

• Do not change any line in the preamble unless it is to (un)comment the \def\tcbox{} line;

• Define the problem type on the line \pbtype{type};

• Do not include more than one problem per file;

• Name the file after the problem number (e.g. problem12.tex);

• Name extra files to be included (e.g. pictures) after the problem number (e.g. problem12a.jpg, problem12b.jpg, etc.);

• Do not forget to update the label of the LATEX environments (e.g. Algorithm, figure, etc.);

• When a problem features more than one algorithm write a very short paragraph listing them. Then study each of them sequentially, i.e. complete the presentation of the first one before getting to the description of the second one.

Note: this also requires some manual adjustments to the LATEX labels (\label{alg:11a}, and \label{alg:11b} if a problem features two algorithms);

2

Failing to comply with the above requirements will lead to a −10% deduction.

2.2 Implementation

For part 1 and 2 of the project the submissions can feature some optional implantations of the studied algorithms. If they respect the following requirements they can bring a large bonus on the project. The implementation

• Must be completed in Python;

• Should take advantage of the specifics of python to achieve better efficiency, cleaner, or more compact code (e.g. lambda functions, decorators, iterators, generators, polymorphism, etc.)

• Should not be a straight-forward rewriting of the algorithm described in the catalog;

• Must be presented during the lab and feature clear explanations regarding what Python specifics were used and why;

Remark: no bonus will be granted if a work is of low quality (e.g. bad coding style or quality, too simple, etc.)

2.3 References

It is of a major importance to include references for each task. Whether writing for the catalog of implementing a work should never be a verbatim copy of any original content.

For the catalog a work is expected to take the form of a summary or a paraphrasing. Never should it be a direct copy of an original content. Not doing so will automatically conduct its author to face the Honor Council. Similarly changing the name of a few variables or adding comments to an available code will be counted as an Honor Code violation.

3

Problems

3.1

Data structures

Easy to study:

1.

Adjacency lists and adjacency matrices

3.

Priority queues

2.

Dictionaries (maps, multi-maps)

4.

Union-Find

Not hard to study:

5.

Bloom filters

7.

Generalized suffix trees

6.

Fibonacci heaps (note: hard, done in labs)

8.

Kd-Trees

3.2 Combinatory

Easy to study:

3

9.

Calendar generation

12.

SAT

10.

Generating graphs

13.

Searching

11.

Generating permutations

14.

Sorting (Merge sort, quick sort, heap sort)

Not hard to study:

15.

Generating Partitions

16.

Generating Subsets

3.3 Graph

Easy to study:

17. Graph traversal

18. Maximally-matchable edges

Not hard to study:

21. All-pairs shortest path

22. Clique problem

23. Closure problem

24. Color coding

25. Dulmage-Mendelsohn decomposition

26. Graduation problem

27. Graph coloring

28. Hitchcock Transport problem

29. Level ancestor problem

19. Prufer sequence

20. Subtree isomorphism

30. Matching

31. Matching preclusion

32. Maximum cardinality matching

33. Path finding

34. Single source shortest path

◦ Directed and non-directed graphs

◦ Non-negative and real weights

35. Traveling salesman problem

36. Vertex independent set

3.4

Mathematics

Easy to study:

37.

Determinant of a matrix

42.

Matrix multiplication

38.

Fast/Discrete Fourier Transform

43.

Miller-Rabbin

39.

Gaussian elimination

44.

Modular exponentiation

40.

GCD and Bezout’s identity

45.

Newton’s method

41.

Karatsuba’s multiplication

46.

Polynomial evaluation (Horner)

Not hard to study:

47.

Interpolation

51.

Simplex method

48.

Intersection detection

52.

Square roots mod p (Tonelli-Shanks)

49.

Matrix inversion (Cholesky, Levinson-Durbin)

50.

Random number generation

53.

Triangulation

Hard to study:

4

54.

Factorization (Multi Precision Quadratic Sieve)

56. Shortest vector

55.

Primality testing (AKS)

3.5 Networks

Easy to study:

57. Back-pressure routing

58. Class-based queueing

59. Deficit round robin

60. Distance-vector routing

61. Fair queueing

62. Flood search routing

63. Link-state routing

3.6 Strings

Easy to study:

70. Edit distance problem

71. Set cover

72. Set packing

Not hard to study:

75. Finite state machine minimization

76. Longest common substring

3.7 Artificial Intelligence

Easy to study:

78. Adaboost

79. DBSCAN

80. Expectation Maximization†

81. Genetic Algorithm†

82. Gradient descent

◦ Gradient-based Optimization

◦ Constrained Optimization

83. Hidden Markov Model

◦ Filtering

◦ Smoothing

◦ Most Likely Explanation

84. K-means Clustering

64. Maximum throughput scheduling

65. Max-min Fairness

66. MENTOR routing

67. Random early detection

68. Token bucket / leaky bucket

69. Traffic shaping

73. String matching

74. Text compression

77. Shortest common superstring

85. K-nearest Neighbor

86. Language Model

87. Logistic Regression with Regularization†

88. Naive Bayesian Classification

89. Neural Network†

◦ Forward Propagation

◦ Backward Propagation

90. Markov Chain Monte Carlo (Inference in Bayesian networks)

91. Minmax Algorithm (with alpha-beta pruning)

92. PageRank

93. Policy Gradient

5

94. Q learning

95. Simulated Annealing†

Not hard to study:

97. A∗ Search

98. Approximate Inference

◦ MAP Inference

◦ Sparse coding

99. Auto-encoders

◦ Regularized

◦ Denoising

◦ Contractive

100. Boltzmann Machines (restricted, deep)

101. Convolutional Neural Network†

◦ Pooling

◦ Batch Normalization

◦ Residual

Hard to study:

112. Generative Adversarial Network

113. Deep Q Learning (with Experience Replay)†

114. Dynamic Memory Network†

115. Faster R-CNN (Region Proposal Networks)†

96. Temporal-difference Learning

102. Deep Belief Network†

103. Discrete Hopfield Network†

104. Gate Bi-directional CNN†

105. Guided Policy Search

106. Monte-Carlo Tree Search†

107. Recurrent Neural Network†

◦ GRU

◦ LSTM

108. Sparse Auto-encoder†

109. Spectral Clustering

110. Support Vector Machine

111. Turney Algorithm

116. SSD†

117. Trust Region Policy Optimization†

118. YOLO†

3.8

Images

Easy to Study:

119.

Image cropping

122.

Image rotation

120.

Image flipping

123.

Watershed

121.

Image resizing

Not hard to study:

124.

Edge detection

127.

Image enhancement

• Roberts

128.

Image thinning

• Canny

129.

Mean shift

• Prewitt

130.

Unsharp masking

• Sobel

125.

Gabor Filter

131.

Lens distortion

126.

Gaussian blur

132.

Impulse denoising filter

Hard to study:

6

133.

Harris Detector

136.

PNG (Encoding and Decoding)

134.

JPEG (Encoding and Decoding)

137.

SIFT

135.

Lempel Ziv Welch

7