C++辅导：Program, Algorithms and Data Structures解析C/C++编程

。，Graph。

Basic

Week 1

• Write a function that randomly shuffles an array of integers and explain the rationale behind its implementation.
• Count the number of trailing 0s in a factorial number.

Week 2

• Write the pseudocode for a function which returns the highest perfect square which is less or equal to its parameter (a positive integer). Implement this in a programming language of your choice.
• Look back at last week’s tasks. Describe the run-time bounds of these algorithms using Big O notation.
• Write the pseudocode corresponding to functions for addition, subtraction and multiplication of two matrices, and then compute A=BC –2(B+C), where B and C are two quadratic matrices of order n. What is the run-time?

Week 3

• Write the pseudocode and code for a function that reverses the words in a sentence. Input: “This is awesome” Output: “awesome is This”. Give the Big O notation.
• Write a recursive function (pseudocode and code) to check if a number n is prime (hint: check whether n is divisible by any number below n).
• Write a recursive function (pseudocode and code) that removes all vowels from a given string s. Input: “beautiful” Output: “btfl”.

Week 4

• Adapt the binary search algorithm so that instead of outputting whether a specific value was found, it outputs whether a value within an interval (specified by you) was found. Write the pseudocode and code and give the time complexity of the algorithm using the Big O notation.
  Example input: L = [2,3,5,7,9,13] low= 10 high = 14 Output: True

Week 5

• Given a sequence of n integer numbers, extract the sub-sequence of maximum length which is in ascending order.
• Based on the Python code or the C++ code provided in class as a starting point, implement the double linked list node delete function.

Week 6

• Implement TREE_SORT algorithm in a language of your choice, but make sure that the INORDER function is implemented iteratively.

Week 7

• Write the pseudocode for an unweighted graph data structure. You either use an adjacency matrix or an adjacency list approach. Also, write a function to add a new node and a function to add an edge. Following that, implement the graph you have designed in the programming language of your choice. You may use your own linked list from previous labs, the STL LL, or use a simple fixed size array (10 elements would be fine).
• Implement BFS and DFS traversals for the above graph. Save the nodes traversed in sequence to a text file.

Week 8

• Implement Dijkstra’s algorithm for a weighted graph data structure (you have to update your previous data structure so that it can deal with weights).

Advanced

Week 1

• Write a program to predict the number of creatures in a fictional alien invasion. An alien lays X eggs each day (there are no genders in this species) and the eggs hatch after Y days. If X is 3 and Y is 5, how many aliens will there be 30 days after a single alien invades?
• A sparse matrix is a matrix where the number of elements which are zero is bigger than the number of elements which are not zero. Find a way to store sparse matrices, and write the functions to add, subtract, and multiply pairs of such matrices. Do not use predefined functions for the operations on matrices in your programming language of choice.

Week 2

• Given two strings of n and m integer elements, write the pseudocode to compute:
  • The string that contains all the elements belonging to both strings.
  • The string of all the elements of the two given strings, written once.
  • The string of the elements from the first string, without the elements that are also in the second string. What’s the run time?
• Write the pseudocode for a recursive program to generate the Cartesian product (product
  set, direct product, cross product) of n sets.
• In addition to the normal homework task, write a function that takes four parameters representing the constant and multiplier of two linearly growing (as in O(m × n + k) ) functions and determines the critical value of n (which should be an integer) at which the relative run-time of the two algorithms switches. That is, at which input size is algorithm A slower than B and at which is B slower than A? Use an iterative approach rather than solving the equations.

Week 3

• Consider having n cubes, each being characterized by their edge length and their colour. Use the cubes (not necessarily all of them) in order to build a tower of maximum height, under the following conditions:
  • any two neighbouring cubes must be of different colours.
  • the edge length of a cube is lower than the edge length of the cube placed below it.

Week 4

• Let’s consider a labyrinth as a n × m matrix, where the corridors are denoted by 1s situated in consecutive positions on the same line or column. The rest of the elements are 0. Within the labyrinth, a person is considered to be in position (i, j). Write a program that lists all exit routes which do not pass the same place twice. Input: n, m, the rows of the matrix, the coordinates of the exit and the coordinates of the person (row, column). Output: a sequence of row/column pairs representing the person’s successive position.
• Adapt the quick sort algorithm to find the mth smallest element out of a sequence of n integers.

Week 5

• Write a function to calculate the kth power of a square matrix, using pointers to access to the elements of the matrix. The resulted matrix will be displayed in natural form.
• Using the model of a circular single-linked list, implement the following scenario: N children stand in a circle; one of the children starts counting the others clockwise. Every Nth child leaves the game. The winner is the one who remains.
  Notes: Read the number of children, the childrens’ names and the one starting to count from the standard input. Input: 4; Diana, Michael, David, Mary; Start: Diana; Winner: Michael.

Week 6

• Build a Binary Search Tree (BST) to hold English language words in its nodes. Use a paragraph of any text in order to extract words and to determine their frequencies. Input: You should read the paragraph from a suitable file format, such as .txt. The following tree operations should be implemented: a) Printing the tree in pre-order. b) Finding a word. Regardless whether found or not found your program should output the path traversed in determining the answer, followed by yes if found or no, respectively.

Week 7

• Implement the structure for an unweighted, undirected graph G, where nodes consist of positive integers. Also, implement a function isPath(v, w), where v and w are vertices in the graph, to check if there is a path between the two nodes. The path found will be printed to a text file as a sequence of integer numbers (the node values).
• Using the graph structure previously implemented, implement a function isConnected(G) to check whether or not the graph is strongly connected. The output should be simply ‘yes’ or ‘no’.

Week 8

• Consider the structure of a directed weighed graph. Implement an algorithm to find its maximum cost spanning tree. The output should be the pre-order and post-order traversal of the tree. Describe the running time of this algorithm.