算法設(shè)計與分析 實驗教學(xué)大綱

PAGE2 算法設(shè)計與分析實驗大綱 數(shù)據(jù)結(jié)構(gòu)實驗課程大綱 PAGE3《算法設(shè)計與分析實驗》課程教學(xué)大綱課程代碼：****課程負責(zé)人：****課程中文名稱：算法設(shè)計與分析實驗課程英文名稱：Algorithmdesignandanalysisexperiment課程類別：必修課程學(xué)分數(shù)：0.5課程學(xué)時數(shù)：15～21授課對象：計算機科學(xué)與技術(shù)及相關(guān)專業(yè)本科本課程的前導(dǎo)課程：C/C++程序設(shè)計、離散數(shù)學(xué)、算法設(shè)計與分析一、教學(xué)介紹算法設(shè)計與分析實驗是算法設(shè)計與分析的配套課程，主要通過上機編程鞏固算法設(shè)計與分析的基本原理和方法，掌握數(shù)據(jù)組織和算法設(shè)計和實現(xiàn)技術(shù)，培養(yǎng)綜合運用算法設(shè)計與分析策略高效解決問題的能力。主要窮舉法、歸納法、迭代法和遞歸法等基本算法設(shè)計方法以及分治法、蠻力法、回溯法、分支限界法、貪心法和動態(tài)規(guī)劃法等算法設(shè)計策略。二、教學(xué)目的算法設(shè)計與分析實驗課程的總目標(biāo)是培養(yǎng)學(xué)生能夠根據(jù)需要開展實驗研究，正確地描述數(shù)據(jù)和組織數(shù)據(jù)，并應(yīng)用數(shù)據(jù)處理方法，編寫程序，分析實驗結(jié)果以獲得合理有效的結(jié)論，具備解決復(fù)雜工程問題的能力。算法設(shè)計與分析實驗分為單機實驗和在線編程。單機實驗是在自己計算機或者實驗室計算機上完成，目的讓學(xué)生領(lǐng)會算法的原理、驗證算法的正確性和采用常用的算法策略求解問題。在線編程實驗是在LeetCode、POJ或者HDU在線編程平臺中完成，目的是培養(yǎng)學(xué)生研究問題、合理地選擇數(shù)據(jù)結(jié)構(gòu)和算法策略構(gòu)建解決方案，并分析比較各種方案優(yōu)劣的能力。三、實驗基本要求與方式1、基本要求課前：要求任課教師布置好實驗題目、實驗要求和實驗?zāi)康?，要求實驗教師為實驗準備好必須的設(shè)備和軟件；要求學(xué)生提前編寫完成實驗要求的程序代碼。課中：要求任課教師隨時解答學(xué)生提出的實驗問題，同時要注重啟發(fā)和引導(dǎo)學(xué)生，使學(xué)生養(yǎng)成獨立思考、解決問題的能力，檢查學(xué)生的實驗內(nèi)容；實驗教師要及時解決實驗設(shè)備可能出現(xiàn)的故障，保證實驗順利地進行。學(xué)生則應(yīng)該按照實驗要求，認真編寫和調(diào)試源代碼，完成實驗內(nèi)容。課后：提交實驗報告。2、實驗方式單機實驗題：輸入相應(yīng)的數(shù)據(jù)，通過檢測輸出結(jié)果，驗證是否實現(xiàn)了實驗的要求。在線編程題：在在線編程平臺提交代碼，查看提交結(jié)果，分析代碼運行的時間和空間。四、實驗報告實驗報告按學(xué)院要求格式書寫，包含封面（含學(xué)號，姓名等），目錄，每個實驗的題目，解答思路，程序框架，源代碼，提交結(jié)果圖（在線編程題給出包含提交通過、運行時間和空間的截屏圖），實驗體會（選）。五、實驗內(nèi)容與學(xué)時分配說明：所有實驗題的題目描述見《教材》，在線編程實驗題目見LeetCode（）、北京大學(xué)POJ和杭州電子科技大學(xué)HUD網(wǎng)站。實驗1：常用數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用學(xué)時數(shù)：0～3。任課教師根據(jù)學(xué)生情況在以下各種類型的實驗題目中選擇若干實驗題目。1.單機實驗題（1）高效地插入、刪除和查找（2）一種特殊的隊列（3）方塊操作2.在線編程題（1）LeetCode328—奇偶鏈表（2）LeetCode394—字符串解碼（3）LeetCode215—數(shù)組中的第k個最大元素（4）HDU1280—前m大的數(shù)（5）POJ2236—無線網(wǎng)絡(luò)實驗2：基本算法設(shè)計方法學(xué)時數(shù)：0～3。任課教師根據(jù)學(xué)生情況在以下各種類型的實驗題目中選擇若干實驗題目。1.單機實驗題（1）最長重復(fù)子串（2）求子矩陣元素和（3）求n階螺旋矩陣（4）驗證梵塔問題2.在線編程題（1）LeetCode344—反轉(zhuǎn)字符串（2）LeetCode206—反轉(zhuǎn)鏈表（3）LeetCode24—兩兩交換鏈表中的結(jié)點（4）LeetCode62—不同路徑（5）HDU1003—最大子序列和（6）HDU1143—三平鋪問題（7）POJ2231—奶牛的總音量（8）POJ1050—最大子矩形實驗3：分治法學(xué)時數(shù)：3。任課教師根據(jù)學(xué)生情況在以下各種類型的實驗題目中選擇若干實驗題目。1.單機實驗題（1）將一個整數(shù)數(shù)組劃分為兩個和差最大的子數(shù)組（2）四路歸并排序（3）查找假幣問題（4）求眾數(shù)（5）求漢諾塔Ⅱ（6）求Fibonacci數(shù)列2.在線編程題（1）LeetCode240—搜索二維矩陣II（2）LeetCode35—搜索插入位置（3）LeetCode33—搜索旋轉(zhuǎn)排序數(shù)組（4）LeetCode162—尋找峰值（5）HDU2141—能否找到X（6）HDU2199—解方程（7）HDU1040—排序（8）HDU1157—求中位數(shù)（9）HDU1007—套圈游戲（10）POJ2255—由二叉樹中序和先序序列產(chǎn)生后序序列（11）POJ1854—轉(zhuǎn)換為回文的交換次數(shù)（12）POJ1995—求表達式值實驗4：回溯法學(xué)時數(shù)：3。任課教師根據(jù)學(xué)生情況在以下各種類型的實驗題目中選擇若干實驗題目。1.單機實驗題（1）象棋算式（2）子集和（3）迷宮路徑（4）哈密頓回路2.在線編程題（1）LeetCode216—組合總和III（2）LeetCode39—組合總和（3）3.LeetCode131—分割回文串（4）HDU1027—第k小的排列（5）HDU2553—N皇后問題（6）HDU2616—殺死怪物（7）POJ3187—向后數(shù)字和（8）POJ1321—棋盤問題（9）POJ2488—騎士游歷（10）POJ1040—運輸問題（11）POJ1129—最少頻道數(shù)實驗5：分支限界法學(xué)時數(shù)：3。任課教師根據(jù)學(xué)生情況在以下各種類型的實驗題目中選擇若干實驗題目。1.單機實驗題（1）原始森林中解救A（2）裝載問題（3）最小機器重量設(shè)計問題Ⅰ（4）最小機器重量設(shè)計問題Ⅱ（5）貨郎擔(dān)問題2.在線編程題（1）LeetCode847—訪問所有結(jié)點的最短路徑（2）LeetCode1376—通知所有員工所需的時間（3）HDU1242—救援問題（4）HDU1548—奇怪的電梯（5）HDU1869—六度分離（6）HDU2425—徒步旅行（7）HDU1072—變形迷宮（8）POJ2312—坦克游戲?qū)嶒?：貪心法學(xué)時數(shù)：3。任課教師根據(jù)學(xué)生情況在以下各種類型的實驗題目中選擇若干實驗題目。1.單機實驗題（1）蓄欄保留問題（2）刪數(shù)問題（3）求所有最小生成樹（4）改進Dijkstra算法（5）字符串的編碼和解碼2.在線編程題（1）LeetCode455—分發(fā)餅干（2）LeetCode135—分發(fā)糖果（3）LeetCode56—合并區(qū)間（4）HDU2037—看電視節(jié)目（5）HDU1009—老鼠的交易（6）HDU3177—裝備問題（7）HDU2111—取寶貝（8）POJ2376—分配清潔班次（9）POJ2726—假日酒店（10）POJ1328—安裝雷達實驗7：動態(tài)規(guī)劃學(xué)時數(shù)：3。任課教師根據(jù)學(xué)生情況在以下各種類型的實驗題目中選擇若干實驗題目。1.單機實驗題（1）矩陣最小路徑和（2）雙核處理問題（3）劃分集合為和相等的兩個子集合（4）員工分配問題2.在線編程題（1）LeetCode64—最小路徑和（2）LeetCode1289—下降路徑最小和II（3）LeetCode638—大禮包（4）LeetCode139—單詞拆分（5）LeetCode377—組合總和Ⅳ（6）LeetCode354—俄羅斯套娃信封問題（7）LeetCode583—兩個字符串的刪除操作（8）LetCode122—買賣股票的最佳時機II（9）HDU2602—收集物品（10）HDU1114—存錢罐（11）HDU2044—一只小蜜蜂（12）POJ1050—最大子矩形和（13）POJ1157—花店（14）POJ1159—回文