# CS代考：Algorithm and Data Structure Analysis COMPSCI 2201

### 关于Algorithm算法

1. 输入- 应该有 0 个或多个从外部提供给算法的输入。
2. 输出- 应该至少获得 1 个输出。
3. 确定性——算法的每一步都应该清晰明确。
4. 有限性——算法应该有有限的步数。
5. 正确性——算法的每一步都必须生成正确的输出。

• 时间复杂度
• 空间复杂度

### CS代考案例：COMPSCI 2201算法和数据结构，80+高分通过

Question 1:

• A hash function, h(x), hashes a name, x (the hash key), onto a hash value (the index into an array) as listed in the following table. The hash table has a length of 10 (indexed from 0 to 9). The keys are inserted into a hash table in the order listed in the following table.

Show the table contents after insertion with:

i. chaining

ii. linear probing

(b) In lectures, on insertion into a skiplist we flipped a coin until a head occured to determine the height of an element. So for example, if we flipped two tails before a head then we would insert an element of height 3. In all the examples in lectures the probability of flipping a head was exactly 1/2.

Now assume that the coin is biased so the probability of flipping a head on a given throw is now 9/10. Derive an expression for the probability of producing an element of height h with this biased coin. Describe in broad terms the consequence of this bias in terms of the average cost of insertion into the skiplist.

Question 2

(a) What is the average cost of find on a binary search tree generated by the insertion of the elements:

10, 1, 6, 9, 7, 3, 2, 8, 4, 5

into an empty tree. Show your working. Note, you can give your answer as a fraction (no need to reduce it to decimal form).

• Prove by induction that a tree with n nodes has n-1 edges. (c) Draw a sequence of diagrams showing the insertion of the values:

[1,3,8,2,7,9,6,4,5] into an empty AVL tree, in the order shown above.

You must:

• Show the resulting tree immediately after each insertion step (that is before any balancing has taken place).

• Indicate the node(s) at which each rotation is performed.

• Where there is a double rotation, show the tree after each single rotation.

• Show the resulting tree after balancing operation(s).

Question 3：

(a) Write pseudo-code for an algorithm that performs breadth-first search of a directed graph: G = (V, E) and prints out all of the nodes visited.

• The following questions relate to traversals of directed graphs i. The graph-search algorithms shown in lectures always keep track of visited nodes because failing to do so can result in non-termination. Draw a graph that will lead to non-termination of Depth-FirstSearch if we fail to keep track of nodes already visited.
• ii. Under what conditions can the Single-Source-Shortest-Path problem be solved using Breadth-First-Search?
• (c) State the storage requirements of a graph with n nodes and m edges using: 1. an adjacency list, and 2. an adjacency matrix briefly justify each answer.

## Recent Case

### 盘点留学生常用5 种最佳笔记方法，哪一种适合您

SCI期刊论文的发表过程是一项复杂而细致的工作，涉

### 轻松掌握万能Essay模板，撰写一篇合格的英文论文

Python可谓是当下最火的编程语言，同时，Pyt