教案教案PAGE5算法設計與分析基礎(Java)PAGE8算法設計與分析課程教案總課堂學時：44目前各個高校都存在算法設計與分析課程學時少、內容多的情況，老師可以針對實際情況調整知識點，建議如下。（1）學時少于36：教學中主要講授五大算法策略，包括第1章，第4～8章，重點為各種經典算法的設計思路，少講算法實現(xiàn)細節(jié)。（2）學時為36～52：教學中可以選擇部分經典算法進行講授，相關實戰(zhàn)題等可以引導學生自學，但要注意知識點的完整性，例如重點講授采用各種算法策略求解0/1背包問題，讓學生體會各種算法策略的要點。（3）學時多于52：教學中講授盡可能多的知識點，但要突出重點，同一個知識點重點講授兩個左右的經典算法，可以適當講授一些實戰(zhàn)題（特別是LeetCode題目），激發(fā)學生在線編程的興趣。建議：引導學生（或者學生小組）做一些專題研究，特別是利用LeetCode中相關題目做驗證工作，例如：（1）求無序序列中第k小元素的算法設計。（2）二分查找算法及其應用。（3）歸并排序算法及其應用。（4）優(yōu)先隊列及其在算法設計中的應用。（5）采用各種算法策略求0/1背包問題。（6）采用各種算法策略求貨郎擔問題。（7）采用各種算法策略求任務分配問題。（8）求冪集問題的各種算法設計。（9）求全排列問題的各種算法設計。（10）為什么采用貪心法求0/1背包問題是錯誤的。（11）基于子集樹框架的問題求解。（12）基于排列樹框架的問題求解。（13）廣度優(yōu)先算法及其應用。（14）利用剪支提高算法性能。（15）求最短路徑問題的研究（LeetCode網站有大量的類似應用題目）。（16）基于0/1背包問題的問題求解（LeetCode網站有大量的類似應用題目）。（17）基于完全背包問題的問題求解（如零錢兌換LeetCode332等）。第1章緒論（共2學時）課次：1（2學時）（1）對應章：第1章概論。（2）教學內容：算法的概念和算法時空分析。（3）教學方式：課堂講授。（4）教學重點：算法時空分析。（5）教學難點：算法時間復雜度漸進符號O、和。（6）教學過程：以若干示例為基礎講授算法時間和空間分析方法。（7）作業(yè)：概論部分的若干問答題和算法分析題。第2章常用數(shù)據(jù)結構及其應用（共4學時）課次：2（2學時）（1）對應章：第2章常用數(shù)據(jù)結構及其應用。（2）教學內容：線性表、字符串、棧、雙端隊列、隊列、優(yōu)先隊列。（3）教學方式：課堂講授+自學。（4）教學重點：Python中列表、字符串、字典、集合、deque、heapq等數(shù)據(jù)類型的應用。（5）教學難點：如何利用各種Python數(shù)據(jù)類型設計求解相關問題的算法。（6）教學過程：以若干示例為基礎講授數(shù)據(jù)結構應用算法設計。（7）作業(yè)：無。課次：3（2學時）（1）對應章：第2章常用數(shù)據(jù)結構及其應用。（2）教學內容：二叉樹、圖、二叉排序樹、平衡二叉樹和哈希表，設計好的數(shù)據(jù)結構。（3）教學方式：課堂講授+自學。（4）教學重點：TreeMap、TreeSet、HashMap和HashSet等數(shù)據(jù)結構集合的應用。（5）教學難點：Tree和Hash的應用場合，如何利用數(shù)據(jù)結構集合高效地設計求解相關問題的算法。（6）教學過程：以若干示例為基礎講授利用數(shù)據(jù)結構求解問題的方法。由于時間限制，可以重點講授TreeMap和HashMap的相關示例，其他引導學生自學。（7）作業(yè)：本章若干問答題和算法設計題。（8）實驗：根據(jù)學生層次選擇一些在線編程題目。第3章基本算法設計方法（共4學時）課次：4（2學時）（1）對應章：第3章基本算法設計方法。（2）教學內容：窮舉法、歸納法和迭代法。（3）教學方式：課堂講授+自學。（4）教學重點：窮舉法、歸納法和迭代法求解問題的思路。（5）教學難點：如何優(yōu)化窮舉法算法和利用歸納法建立求解問題的遞推關系。（6）教學過程：通過示例講授三種基本算法設計方法。由于時間限制，可以重點講授求最大連續(xù)子序列和多數(shù)元素示例，其他引導學生自學。（7）作業(yè)：無課次：5（2學時）（1）對應章：第3章基本算法設計方法。（2）教學內容：遞歸法和遞推式計算。（3）教學方式：課堂講授+自學。（4）教學重點：如何建立求解問題的遞歸模型。（5）教學難點：遞歸算法分析。（6）教學過程：通過示例講授遞歸算法設計方法及其時間復雜度分析。由于時間限制，可以重點講授求全排列示例，其他引導學生自學。（7）作業(yè)：本章若干問答題和算法設計題。（8）實驗：根據(jù)學生層次選擇一些在線編程題目。第4章分治法（共6學時）課次：6（2學時）（1）對應章：第4章分治法。（2）教學內容：分治法概述，求解排序問題。（3）教學方式：課堂講授。（4）教學重點：分治法的基本策略和框架，快速排序和歸并排序。（5）教學難點：各種分治排序算法的應用。（6）教學過程：通過示例講授分治法在排序問題中的應用。（7）作業(yè)：無課次：7（2學時）（1）對應章：第4章分治法。（2）教學內容：求解查找問題。（3）教學方式：課堂講授+自學。（4）教學重點：二分查找，二分查找擴展，查找假幣問題（三分查找）。（5）教學難點：各種分治查找算法的應用。（6）教學過程：通過示例講授分治法在查找問題中的應用。（7）作業(yè)：無課次：8（2學時）（1）對應章：第4章分治法。（2）教學內容：求解組合問題。（3）教學方式：課堂講授。（4）教學重點：最大子序和，多數(shù)元素，求最近點對距離。（5）教學難點：各種分治組合算法的應用。（6）教學過程：通過示例講授分治法在組合問題中的應用。（7）作業(yè)：本章若干問答題和算法設計題。（8）實驗：根據(jù)學生層次選擇一些在線編程題目。第5章回溯法（共6學時）課次：9（2學時）（1）對應章：第5章回溯法。（2）教學內容：問題的解空間，回溯法框架，深度優(yōu)先搜索。（3）教學方式：課堂講授。（4）教學重點：解空間的概念，圖的深度優(yōu)先遍歷和回溯法的不同點。（5）教學難點：圖的深度優(yōu)先遍歷和回溯法的不同點。（6）教學過程：通過示例講授深度優(yōu)先搜索和回溯算法的執(zhí)行過程。（7）作業(yè)：無。課次：10（2學時）（1）對應章：第5章回溯法。（2）教學內容：基于子集樹框架的問題求解。（3）教學方式：課堂講授+自學。（4）教學重點：基于子集樹框架求解子集和問題，簡單裝載問題，0/1背包問題，完全背包問題，圖的m著色問題，n皇后問題和任務分配問題。（5）教學難點：子集樹框架中的剪支操作。（6）教學過程：從子集和問題的左右剪支到0/1背包問題的左右剪支講授如何設計剪支操作。由于時間限制，簡單裝載問題和n皇后問題引導學生自學。（7）作業(yè)：無。課次：11（2學時）（1）對應章：第5章回溯法。（2）教學內容：基于排列樹框架的問題求解。（3）教學方式：課堂講授。（4）教學重點：基于排列樹