教學大綱 Syllabus

科目名稱:演算法

Course Name: Algorithms

修別:必

Type of Credit: Required

3.0

學分數

Credit(s)

75

預收人數

Number of Students

課程資料Course Details

課程簡介Course Description

演算法的思維影響電腦系統的效能。尤其在Big Data, AI的時代,演算法的思維更加重要。矽谷科技公司在面試時,往往都會要求解題。台灣的公司近年來也逐漸開始參考類似方式。因此軟體工程師求職前往往都會練習刷題。解題的能力,除了程式的基礎,另一個關鍵就是「演算法」的思維。

因此,「演算法」這門課主要在介紹
1. 演算法如何設計、如何構思
2. 演算法背後的思維
3. 如何應用演算法

核心能力分析圖 Core Competence Analysis Chart

能力項目說明


    課程目標與學習成效Course Objectives & Learning Outcomes

    演算法程目學習透演算法設計以解決 Computer Science 的問題,並體會演算法設計的樂趣。包括
    1. 演算法如何設計如何
    2. 演算法背後的思維精神
    3. 如何用實作演算法

     

    每周課程進度與作業要求 Course Schedule & Requirements

    教學週次Course Week 彈性補充教學週次Flexible Supplemental Instruction Week 彈性補充教學類別Flexible Supplemental Instruction Type
    第1週 Introduction (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)
    • Review of Data Structures
    第2週 Data Structures and Algorithms (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)
    • Review of Induction Techniques
    • Review of Algorithm Design Strategy
    • Divide and Conquer
    • Greedy Algorithm
    • Dynamic Programming
    第3週 Design of Algorithm by Induction (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)
    • Skyline Problem
    • Balance Factor in Binary Tree
    • Finding Maximum Consecutive Subsequence
    • Knapsack Problem

    第4週 Algorithms Involving Sequence and Sets (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)

    • Binary Search
    • Finding Minimum in Cyclic Sorted Sequence
    • Binary Search of Unknown Size
    • Stuttering-Subsequence
    • Solving Equation: Bisection Algorithm
    • Interpolation Search

    第5週 Algorithms Involving Sequence and Sets (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)

    • Bucket sort
    • Radix sort
    • Insertion sort
    • Selection sort
    • Bubble sort
    • Merge sort
    • Quick sort
    • Heap sort
    • Heap Construction: Top Down vs. Bottom Up Approaches
    • Low bound of Comparison-based Sorting
    • External Sorting
    • Sorting of Large Structures
    • Finding both Maximum and Minimum Elements
    • Finding the K-th Smallest Element
    • String Editing Distance: Levenshtein Distance, Damerau–Levenshtein distance

    第6週 Algorithms Involving Sequence and Sets (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)

    • Longest Common Subsequence
    • Sequence Alignment
    • Dynamic Time Warping
    • String Matching: KMP Algorithm
    • Huffman Tree
    第7週 Graph Algorithms (I) (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.) 
    • Graph Traversal: DFS
    • Finding Connected Components
    • DFS Numbering, DFS Tree
    • Finding a Cycle in a Graph
    • Graph Traversal: BFS

    第8週 Midterm Exam.

    第9週 Graph Algorithms (II) (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)

    • Review of Midterm Exam.
    • Topological Ordering
    • Unweighted Shortest Paths
    • Weighted Shortest Paths of Directed Acyclic Graph
    • Weightes Shortest Paths of Directed Cyclic Graph without Negative Weight: Dijkstra's Algorithm

    第10週 Graph Algorithms (III) (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)

    • All Pair Shortest Paths: Floyd-Warshall Algorithm
    • Minimum Spanning Tree: Prim's Algorithm
    • Minimum Spanning Tree: Kruskal's Algorithm
    • Bipartite Graph Matching

    第11週 Graph Algorithms (IV) (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)

    • Graph Coloring
    • Maximum Flow Problem: Ford–Fulkerson Algorithm
    • Maximum Flow Problem: Edmonds-Karp Algorithm
    • Graph Decomposition: Bocinnected Componnents

    第12週 Geometric Algorithms (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)

    • Computational Geometry
    • Determining Inside a Polygon
    • Constructing Simple Polygons
    • Convex Hull: Straight Forward Approach
    • Convex Hull: Gift Wrapping
    • Convex Hull: Graham's Scan
    • Closest Pair

    第13週 Reduction (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)

    • Reduction of Cyclic String Matching
    • Reduction of System Distinct Representatives
    • Reudction of Sequence Comparison

    第14週 校慶停課(自主總整學習)

    第15週 NP-Completeness (I) (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)

    • Finite-State Machine
    • Push-Down Automata
    • Turing Machine
    • Non-Deterministic Turing Machine
    • Decision Problem vs. Optimization Problem
    • Non-Decidable Problem
    • Non-Deterministic Algorithm

    第16週 NP-Completeness (II) (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)

    • P, NP, and NP Hard
    • NP-Complete
    • P = NP ?
    • Satisfibility and Traveling Salesman Problem
    • Proof of NP-Completeness
    • Techniques Dealing with NP-Complete Problems

    第17週 Final Exam.

    第18週 Advaned Algorithms (線上課程)

     

    授課方式Teaching Approach

    80%

    講述 Lecture

    10%

    討論 Discussion

    10%

    小組活動 Group activity

    0%

    數位學習 E-learning

    0%

    其他: Others:

    評量工具與策略、評分標準成效Evaluation Criteria

    1. 課程要求:建議有興趣修讀本課程的同學,

    (1) 具備程式設計的能力 (C語言)

    (2) 修讀過「資料結構」

    2. 評分將根據

    (1). 期中考

    (2). 期末考

    (3). 6~7次程式作業

     

    指定/參考書目Textbook & References

    Introduction to Algorithms: A Creative Approach, Udi Manber, Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA.

    已申請之圖書館指定參考書目 圖書館指定參考書查詢 |相關處理要點

    維護智慧財產權,務必使用正版書籍。 Respect Copyright.

    課程相關連結Course Related Links

    
                

    課程附件Course Attachments

    課程進行中,使用智慧型手機、平板等隨身設備 To Use Smart Devices During the Class

    需經教師同意始得使用 Approval

    列印